#队列式分支限界法
import queue
class Node:
    def __init__(self,row,col):
        self.row = row
        self.col = col

def findpath(start,finish):
    global grid,offset
    pathLen = 0
    if(start.row==finish.row) and (start.col==finish.col):#起点与终点相同，不用布线
        pathLen = 0
    # return
    here = start
    grid[start.row][start.col]=0
    que = queue.Queue()
    que.put(start)
    while(True):
        here = que.get()
        for i in range(4):#沿着扩展结点的右、下、左、上四个方向扩展
            nbr = Node(here.row + offset[i].row,here.col + offset[i].col)
            #print("nbr.row = "+str(nbr.row))
            #print("nbr.col =" +str(nbr.col))
            if(grid[nbr.row][nbr.col] == -1):#如果这个方格还没有扩展
                grid[nbr.row][nbr.col] = grid[here.row][here.col] + 1
                if((nbr.row == finish.row) and (nbr.col==finish.col)):
                    break  #如果到达终点结束
                que.put(nbr)#此邻结点放入队列
        if((nbr.row==finish.row) and (nbr.col==finish.col)):
            break #完成布线
        if que.empty():
            return

def build_path(grid,start,finish):
    global offset
    pathlen=grid[finish.row][finish.col]
    path = []
    here=finish
    for j in range(pathlen-1,-1,-1):
        path.insert(0,here)
        for i in range(4):#四个方向扩展
            nbr = Node(here.row+offset[i].row,here.col+offset[i].col)
            if (grid[nbr.row][nbr.col]==j):
                break
        here=nbr  #往回推进
    path.insert(0,start)
    return path ,pathlen
